The following discussion centers on embedded systems because their requirements are well understood. Other less-understood systems may have similar requirements
Heaps are well-known structures used in computer systems to provide dynamic memory allocation and deallocation. Due to the simple nature of most embedded systems, until recently, heaps have not been used extensively in them. However, this is changing. Embedded systems are becoming more complex and their need for dynamic memory allocation is increasing.
Embedded systems are characterized by the following requirements:                Deterministic rapid response to events.        Limited resources due to cost and power constraints.        Unattended operation in harsh environments.        Substantial functional variation from one embedded system to the next.        
Linear heaps have been used in embedded systems. Linear heap allocation searches start with the first free chunk and proceed linearly until a big-enough chunk is found. This can be very time consuming for even moderate size heaps, which is not compatible with the real-time deterministic requirements of most embedded systems. Hence linear heaps have been used mainly for one-time allocations during initialization and sparingly for dynamic allocations during operation.
Block pools have been frequently used for dynamic allocations in embedded systems. The problem with block pools is that all blocks in a pool are the same size. Hence, covering a large range of block sizes requires a large number of block pools or it requires blocks to often be much larger than the block needed. Either can be very wasteful of memory, which is not compatible with the limited memory in embedded systems. Block pools have been useful for simple embedded systems that require very few block sizes.
The complexity of embedded systems is growing due to the addition of smartphone-like graphical user interfaces, connection to complex networks, including the IoT, connection to more complex peripherals, and generally more powerful features. With this comes the need for greater memory allocation flexibility within the constraints of embedded systems.
Nearly all prior art including patents, articles, and heaps focuses on heaps for general-purpose systems such as servers, PCs, smart phones, tablets, etc. These systems have gigabytes of memory, megabyte caches, and multi-core processors with gigahertz clock rates. The heaps in these systems are typically hundreds of megabytes in size and have tens of thousands to millions of active chunks.
By contrast, embedded systems have 50 kilobytes to a few megabytes of memory, no cache, and single core processors with 50 to 250 kilohertz clock rates. The heaps in embedded systems typically are tens to hundreds of kilobytes in size with hundreds to thousands of active chunks. Thus, there is a two to three orders of magnitude difference between general purpose systems and embedded systems.
Well-known examples of general-purpose heaps are dlmalloc, ptmalloc2 and 3, glibc malloc, tcmalloc, and nedmalloc. The main focus of these heaps is high performance for a very wide range of applications. Although these heaps use bins, the bins are in rigid structures which do not scale down to embedded systems. In addition, all of these heaps rely upon obtaining more memory from the operating system if they run out—a luxury not available in most embedded systems.
Nor do these heaps address the problem of unattended operation in harsh environments because commercial systems are generally attended and operate in protected environments. And since commercial system programmers have no need to work at the system and hardware levels, as do embedded system programmers, these heaps offer little in the way of low-level debug features to trace heap usage problems.
An article written by Paul R Wilson, et al, “Dynamic Storage Allocation: A Survey and Critical Review” published in 1995 provides a good review of heap research up to that time. The basic finding of this survey is that best results are achieved if the allocator is fit to the application. Since embedded applications vary greatly in requirements, this would imply that an embedded heap should be highly customizable. The article has no discussion of embedded system requirements.
U.S. Pat. No. 5,561,786 to Morse titled “Computer Method and System for Allocating and Freeing Memory Utilizing Segmenting and Free Block Lists” Oct. 1, 1996 teaches dividing a heap into 2^n segments of equal size, each with a free list of its blocks in size order. A size tree with links to free lists is searched to find a free list, which is then searched to find a best fit block. Unfortunately, this patent is focused on garbage collection rather than the needs of embedded systems.
U.S. Pat. No. 6,832,381 to Mathur, et. al., titled Application Program Interfaces and Structures in a Resource Limited Operating System, Dec. 14, 2004 wherein if an embedded system runs out of heap, an API is provided to request that another user (e.g. a task) release the heap memory it is using. This is not consistent with the need for deterministic operation of embedded systems and does not address the problem of configuring the heap for best performance.
U.S. Pat. No. 8,838,928 to Robin, et. al. titled Memory Management and Method of Allocation Using Free-List Sep. 16, 2014 teaches the use of lists of identifiers where each has an associated chunk size and threshold to limit free list size. However, this patent requires an underlying operating system allocator, is wasteful of memory, and the regions have fixed block sizes similar block pools.
In general, patents issued to date address needs such as garbage collection, use in multi-processor systems, power-of-two allocation, variants of block pools, use of binary trees, per thread heaps using large blocks allocated by the underlying operating system, and other solutions not relevant to embedded systems. In summary, current heap solutions fail to address the needs of embedded systems in three important areas:                1. Customization to requirements of individual embedded systems.        2. Low-level debug support.        3. Self-healing.        